package leetcode.treeCode.week5.leetcode_450;

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        return dfs(root,key);
    }

    private TreeNode dfs(TreeNode node, int key) {
        /**
         * 1.没找到节点
         * 2.双空
         * 3.左空
         * 4.右空
         * 5.都不空
         */
        if (node == null) {
            return null;
        }
        if (node.val == key) {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                TreeNode cur = node.right;
                while (cur.left != null) {
                    cur = cur.left;
                }
                cur.left = node.left;
                node = node.right;
            }
        }
        if (node.val > key) {
            TreeNode left = dfs(node.left, key);
            node.left = left;
        }
        if (node.val<key){
            TreeNode right = dfs(node.right, key);
            node.right = right;
        }
        return node;
    }
}